package j20251017;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    int aim;
    List<Integer> path;
    List<List<Integer>> ret;
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        aim=target;
        path=new ArrayList<>();
        ret=new ArrayList<>();
        dfs(nums,0,0);
        return ret;
    }
    public void dfs(int[] nums,int pos,int sum){
        if(sum==aim){
            ret.add(new ArrayList<>(path));
            return;
        }
        if(sum>aim||pos==nums.length){
            return;
        }
        for(int i=pos;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums,i,sum+nums[i]);
            path.remove(path.size()-1);
        }
    }

    StringBuilder path1;
    List<String> ret1;
    public List<String> letterCasePermutation(String s) {
        path1=new StringBuilder();
        ret1=new ArrayList<>();
        dfs(s,0);
        return ret1;
    }
    public void dfs(String s,int pos){
        if(pos==s.length()){
            ret1.add(path1.toString());
            return;
        }
        char ch=s.charAt(pos);
        //不变
        path1.append(ch);
        dfs(s,pos+1);
        path1.deleteCharAt(path1.length()-1);
        //改变
        if(ch<'0'||ch>'9'){
            char tmp=change(ch);
            path1.append(tmp);
            dfs(s,pos+1);
            path1.deleteCharAt(path1.length()-1);
        }
    }
    public char change(char ch){
        if('a'<=ch&&ch<='z') return ch-=32;
        else return ch+=32;
    }

    boolean[] check;
    int count;
    public int countArrangement(int n) {
        check=new boolean[n+1];
        dfs(n,1);
        return count;
    }
    public void dfs(int n,int pos){
        if(pos==n+1){
            count++;
            return;
        }
        for(int i=1;i<=n;i++){
            if(check[i]==false&&(i%pos==0||pos%i==0)){
                check[i]=true;
                dfs(n,pos+1);
                check[i]=false;
            }
        }
    }
}
